package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * MirrorTree
 *
 * @author: lupeng6
 * @create: 2020/12/25 21:21
 */
public class MirrorTree {

    public static void main(String[] args) {
        Integer[] array = new Integer[]{10, 5, 15, 3, 7, null, 18};
        TreeNode root = TreeMain.array2tree(array);
        System.out.println(rangeSumBST(root, 7, 15));
    }

    public static TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode swap = root.left;
        root.left = root.right;
        root.right = swap;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }


    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        TreeNode root = null;

        if (t1 == null) {
            root = new TreeNode(t2.val);
            root.left = mergeTrees(null, t2.left);
            root.right = mergeTrees(null, t2.right);
        } else if (t2 == null) {
            root = new TreeNode(t1.val);
            root.left = mergeTrees(t1.left, null);
            root.right = mergeTrees(t1.right, null);
        } else {
            root = new TreeNode(t1.val + t2.val);
            root.left = mergeTrees(t1.left, t2.left);
            root.right = mergeTrees(t1.right, t2.right);
        }
        return root;
    }

    public static int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        int val = root.val;
        if (val >= low) {
            sum += rangeSumBST(root.left, low, high);
        }
        if (val <= high) {
            sum += rangeSumBST(root.right, low, high);
        }
        if (val >= low && val <= high) {
            sum += val;
        }
        return sum;
    }

    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Node> children = root.children;
        if (children != null && !children.isEmpty()) {
            for (Node child : children) {
                result.addAll(postorder(child));
            }
        }
        result.add(root.val);
        return result;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        helper(root);
        return res;
    }

    public void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.right);
        k--;
        if (k == 0) {
            res = root.val;
        } else {
            helper(root.left);
        }
    }
}
